// https://leetcode.cn/problems/house-robber-ii/description/

// 算法思路总结：
// 1. 处理环形数组的打家劫舍问题
// 2. 分解为两个线性问题：抢首不抢尾、抢尾不抢首
// 3. 对每种情况使用动态规划求最大收益
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }
    
    int robRange(vector<int>& nums, int l, int r) 
    {
        int prev = 0, cur = 0;
        for (int i = l; i <= r; i++) 
        {
            int temp = cur;
            cur = max(cur, prev + nums[i]);
            prev = temp;
        }
        return cur;
    }
};

int main()
{
    vector<int> v1 = {2,3,2}, v2 = {1,2,3,1};
    Solution sol;

    cout << sol.rob(v1) << endl;
    cout << sol.rob(v2) << endl;

    return 0;
}